import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    public long maximumBeauty(int[] flowers, long newFlowers, int target, int full, int partial) {
        Arrays.sort(flowers);
        long ans=0;
        int j=flowers.length-1;
        while(j>=0&&flowers[j]>=target){j--;}//j是第一个小于target的位置
        long preSum[]=new long[flowers.length+1];
        for(int i=1;i<=flowers.length;i++){preSum[i]=preSum[i-1]+flowers[i-1];}
        if(newFlowers>=(long)target*(j+1)-preSum[j+1]){ans=(long)full*flowers.length;}
        for(int i=j+1;i>0;i--){
            if(newFlowers<0){break;}
            ans=Math.max(ans,findMostBeauty(preSum,flowers,i,full,newFlowers,target,partial));
            newFlowers-=target-flowers[i-1];
        }
        return ans;
    }
    public long findMostBeauty(long preSum[],int flowers[],int lastFull,int full,long newFlowers,int target,int partial){
        int l=0,r=lastFull-1;
        while(l<r){
            int mid=(l+r)/2;
            if(newFlowers>=(long)flowers[mid]*mid-preSum[mid]){l=mid;}
            else{r=mid-1;}
            if(l==r-1){
                if(newFlowers>=(long)flowers[r]*r-preSum[r]){l=r;}
                break;
            }
        }
        long remain=newFlowers-((long)flowers[l]*l-preSum[l]);
        long most=Math.min((long)target-1,remain/(l+1)+flowers[l]);
        return (long)full*(flowers.length-lastFull)+most*partial;
    }
}
